package book;

import java.util.Arrays;

public class PrimeCircleSolution {
    // 回溯法求解素数环问题
    public static void primeCircle(int n) {
        // 用数组表示素数环，并初始化为0
        int[] a = new int[n];
        Arrays.fill(a, 0);
        // 定义k为第一个位置，并从位置0填写1开始搜索
        a[0] = 1;         
        int k = 1;   
        // 执行DFS     
        while (k >= 1) {
            // 不断试探下一个数，直到符合题目规则
            a[k] = a[k] + 1;
            while (a[k] <= n) {
                if (check(k, a, n)) break;   
                else a[k] = a[k] + 1; 
            }

            // 找到结果时，直接输出并返回
            if (a[k] <= n && k == n - 1) {
                for (int j = 0; j < n; j++) 
                    System.out.print(a[j] + "   ");
                System.out.println();
                return;
            }

            // 填写下一个位置，或者回溯上一个位置
            if (a[k] <= n && k < n - 1) k++;     
            else a[k--] = 0;
        }
    }

    // 检查当前填写是否满足素数环规则
    public static boolean check(int k, int[] a, int n) {
        // flag为true表示正常向下一级移动，false表示回溯到上一级
        boolean flag = false;  
        // 判断是否重复
        for (int i = 0; i < k; i++) {         
            if (a[i] == a[k]) return flag;
        }
        // 判断相邻数之和是否素数
        flag = isPrime(a[k] + a[k - 1]);  
        //判断第一个和最后一个是否素数 
        if (flag && k == n - 1) flag = isPrime(a[k] + a[0]);  
        return flag;
    }

    // 工具方法：判断x是否素数
    // 本题中需要反复检查两数之和是否为素数，而且范围为20以内的数相加
    // 因此考虑用打表法提高查找效率
    public static boolean isPrime(int x) {
        if (primes == null || primes.length == 0) {
            primes = new boolean[40];
            Arrays.fill(primes, true);
            for (int i = 2; i < 40; i++)
                if (primes[i])
                    for (int j = i * 2; j < 40; j += i)
                        primes[j] = false;
        }
        return primes[x];
    }
    // 素数表：primes[x]表示x是否为素数
    private static boolean[] primes;

    public static void main(String[] args) {
        primeCircle(20);
    }
}